CS254Spring 2017Lecture Notes
Theory of Computation
Videos of lectures are available.
Below are my lecture notes for the class so far.
They should serve as a rough guide to what was covered on any given day.
Frequently, however, I say more in class than is in these notes.
Also, I tend to dynamically correct typos on the board
that might appear in these lecture notes. So caveat emptor.
Week 1: [Jan 30 -- Notation, Languages, Big-Oh] [Feb 1 -- Turing Machines and their Expressive Power]
Week 2: [Feb 6 -- TM Variants and Time Complexity] [Feb 8 -- Universal Turing Machines, Uncomputability]
Week 3: [Feb 13 -- More Uncomputability] [Feb 15 -- O(T log T) Universal Simulation]
Week 4: [Feb 20 -- NP and NP-completeness] [Feb 22 -- NP-completeness]
Week 5: [Feb 27 -- Finish Cook-Levin] [Mar 1 -- NP-completeness, Computing Certificates]
Week 6: [Mar 6 -- Other Complexity Classes, SAT Algorithms][Mar 8 -- More SAT Algorithms]
Week 7: [Mar 13 -- Diagonalization] [Mar 15 -- Ladner's Theorem, Baker, Gill, Solovay's Result]
Week 8: [Mar 20 -- Practice Midterm] [Mar 22 -- Midterm]
Week 9: [Mar 27 -- Spring Break] [Mar 29 -- Spring Break]
Week 10: [Apr 3 -- Space Complexity] [Apr 5 -- Relationships between Space Complexity Classes]
Week 11: [Apr 10 -- Polynomial Hierarchy, Alternation] [Apr 12 -- Time-Space Tradeoffs]
Week 12: [Apr 17 -- Circuits] [Apr 19 -- Finish Circuits]
Week 13: [Apr 24 -- Randomized Complexity Classes] [Apr 26 -- Error Reduction, Relationships Among Randomized Classes]
Week 14: [May 1 -- Interactive Proofs] [May 3 -- Public Versus Private Coins, Set Lower Bound Protocol]
Week 15: [May 8 -- IP=PSPACE, Circuit Lower Bounds] [May 10 -- Lower Bounds for AC^0[q]]
Week 16: [May15 -- Final Review] |